|
|
Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
Pěgřímek, David ; Gregor, Petr (advisor) ; Dvořák, Tomáš (referee)
In 2001 Stephen Locke conjectured that for every balanced set F of 2k faulty vertices in the n-di- mensional hypercube Qn where n ≥ k + 2 and k ≥ 1 the graph Qn − F is hamiltonian. So far the conjecture remains open although partial results are known; some of them with additional conditions on the set F. We explore hamiltonicity of Qn − F if the set of faulty vertices F forms certain isometric subgraph in Qn. For an odd (even) isometric path P in Qn the graph Qn − V (P) is Hamiltonian laceable for every n ≥ 4 (resp. n ≥ 5). Although a stronger result is known, the method we use in proving the theorem allows us to obtain following results. Let C be an isometric cycle in Qn of length divisible by four for n ≥ 6. Then the graph Qn −V (C) is Hamiltonian laceable. Let T be an isometric tree in Qn with odd number of edges and let S be an isometric tree in Qm with even number of edges. For every n ≥ 4, m ≥ 5 the graphs Qn −T and Qm −S are Hamiltonian laceable. A part of the proof is verified by a computer. 1
|
|
|
Rozklady propojovacích sítí na dlouhé cesty
Měkuta, Kryštof ; Gregor, Petr (advisor) ; Dvořák, Tomáš (referee)
❚✐t❧❡✿ P❛rt✐t✐♦♥s ♦❢ ✐♥t❡r❝♦♥♥❡❝t✐♦♥ ♥❡t✇♦r❦s ✐♥t♦ ❧♦♥❣ ♣❛t❤s ❆✉t❤♦r✿ ❑r②➨t♦❢ ▼➙❦✉t❛ ❉❡♣❛rt♠❡♥t✿ ❉❡♣❛rt♠❡♥t ♦❢ ❚❤❡♦r❡t✐❝❛❧ ❈♦♠♣✉t❡r ❙❝✐❡♥❝❡ ❛♥❞ ▼❛t❤❡♠❛t✐❝❛❧ ▲♦❣✐❝ ❙✉♣❡r✈✐s♦r✿ ▼❣r✳ P❡tr ●r❡❣♦r✱ P❤✳❉✳✱ ❑❚■▼▲ ❆❜str❛❝t✿ ❲❡ s✉r✈❡② s♦♠❡ ❜❛s✐❝ ♣r♦♣❡rt✐❡s ♦❢ s❡❧❡❝t❡❞ ✐♥t❡r❝♦♥♥❡❝t✐♦♥ ♥❡t✇♦r❦s✱ ♠♦r❡ ♣r❡❝✐s❡❧② ♠♦❞✐✜❝❛t✐♦♥s ♦❢ ❤②♣❡r❝✉❜❡s✳ ■♥ ♣❛rt✐❝✉❧❛r✱ ✇❡ st✉❞② ❢❛✉❧t✲t♦❧❡r❛♥❝❡ ♦❢ ❛✉❣♠❡♥t❡❞ ❝✉❜❡s ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ❡①✐st❡♥❝❡ ♦❢ ❍❛♠✐❧t♦♥✐❛♥ ❝②❝❧❡s✳ ❲❡ ❛❧✲ s♦ ♣r❡s❡♥t ❛ ♠❡t❤♦❞ t♦ ❝♦♥str✉❝t ♠❛♥② s♣❛♥♥✐♥❣ s✉❜❣r❛♣❤s ♦❢ AQn ✐s♦♠♦r♣❤✐❝ t♦ Qn ✉s✐♥❣ ❡❧❡♠❡♥t❛r② ❢❛❝ts ❢r♦♠ ❧✐♥❡❛r ❛❧❣❡❜r❛✳ ❲❡ ♣r♦✈❡ t❤❛t n✲❞✐♠❡♥s✐♦♥❛❧ ❛✉❣♠❡♥t❡❞ ❝✉❜❡ AQn ✇✐t❤ f ❢❛✉❧t② ❡❞❣❡s ❝♦♥t❛✐♥s ❛ ❝♦♣② ♦❢ n✲❞✐♠❡♥s✐♦♥❛❧ ❤②♣❡r✲ ❝✉❜❡ Qn ✇✐t❤ ❛t ♠♦st n 2n−1 f ❢❛✉❧t② ❡❞❣❡s✳ ❯s✐♥❣ t❤✐s r❡s✉❧t ✇❡ ❛r❡ ❛❜❧❡ t♦ ❡❛s✐❧② tr❛♥s❢❡r s❡✈❡r❛❧ ♣r♦♣❡rt✐❡s ♦❢ Qn ✇✐t❤ ❢❛✉❧t② ❡❞❣❡s t♦ AQn ✇✐t❤ ✭♠♦r❡✮ ❢❛✉❧t② ❡❞❣❡s✳ ❆♣♣❧②✐♥❣ s✐♠✐❧❛r ♠❡t❤♦❞✱ ✇❡ ❛❧s♦ s❤♦✇ t❤❛t ✐❢ f ≤ 3n−7 ❛♥❞ ❡✈❡r② ✈❡rt❡① ♦❢ AQn ✐s ✐♥❝✐❞❡♥t t♦ ❛t ❧❡❛st t✇♦ ♥♦♥✲❢❛✉❧t② ❡❞❣❡s✱ t❤❡♥ AQn ❤❛s ❛ ♥♦♥✲❢❛✉❧t② ❤❛♠✐❧t♦♥✐❛♥ ❝②❝❧❡✳ ▼♦r❡♦✈❡r✱ ✇❡ s❤♦✇ t❤❛t ❡✈❡r② t✇♦ ♠♦♥♦♠♦r♣❤✐s♠s ♦❢ G1 t♦ AQn ❛♥❞ G2 t♦ AQm ❝❛♥ ❜❡ ❝♦♠♣♦s❡❞ ✐♥t♦ ❛ ♠♦♥♦♠♦r♣❤✐s♠ ♦❢ t❤❡ ❈❛rt❡s✐❛♥ ♣r♦❞✉❝t G1 G2 t♦ AQn+m✳ ❑❡②✇♦r❞s✿ ❤②♣❡r❝✉❜❡✱ ❛✉❣♠❡♥t❡❞ ❝✉❜❡✱ ❤❛♠✐❧t♦♥✐❝✐t②✱ ❢❛✉❧t② ❡❞❣❡s
|
|
|
Genetic Approach To Hypercube Problems
Kuboň, David ; Gregor, Petr (advisor) ; Pilát, Martin (referee)
The main focus of this thesis are hypercubes. In the first part, we introduce hypercubes, which form an interesting class of graphs that has practical uses in networks and distributed computing. Because of their varied applications, the thesis describes the graph-theory problems related to hypercubes such as searching for detour spanners, minimizing their maximal degree and finding multiple edge- disjoint spanners. It also overviews current results on selected hypercube problems and proposes a solution using a genetic algorithm. The genetic algorithm is designed, implemented and its performance is evaluated. The conclusion is that applying a genetic algorithm to some hypercube problems is a viable, but not the most effective method.
|
|
|
Construction of Gray codes with special properties
Novotný, Tomáš ; Dvořák, Tomáš (advisor) ; Fink, Jiří (referee)
A (cyclic) Gray code is a (cyclic) sequence of all n-bit strings in which consecutive strings differ in a single bit. Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a cyclic Gray code. An affirmative answer is known for perfect matchings (Fink, 2007) while the ge- neral case is still open. The main contribution of this thesis is a generalization of Fink's result to Gray codes with prescribed ends. The characterization of perfect matchings extendable in this way is verified for n = 5 with the assistance of a com- puter, which is useful as a basis for the inductive proof of the general statement. The other part of the thesis is focused on smallest maximal matchings in hyper- cubes which could possibly form especially hard instances of the Ruskey-Savage problem. We devise a novel method which provides - in particular for small di- mensions - maximal matchings of smaller size than the classical asymptotically optimal construction (Forcade, 1973). An adjusted program from the first part is then applied to test the Ruskey-Savage problem over these matchings, however, the extending Gray code is always discovered. 1
|
|
|
Hamiltonicity of hypercubes without k-snakes and k-coils
Pěgřímek, David ; Gregor, Petr (advisor) ; Fink, Jiří (referee)
A snake (coil) is an induced path (cycle) in a hypercube. They are well known from the snake-in-the-box (coil-in-the-box) problem which asks for the longest snake (coil) in a hypercube. They have been generalized to k-snakes (k-coils) which preserve distances between their every two vertices at distance at most k − 1 in hypercube. We study them as a variant of Locke's hypothesis. It states that a balanced set F ⊆ V (Qn) of cardinality 2m can be avoided by a Hamiltonian cycle if n ≥ m + 2 and m ≥ 1. We show that if S is a k-snake (k-coil) in Qn for n ≥ k ≥ 6 (n ≥ k ≥ 7), then Qn − V (S) is Hamiltonian laceable. For a fixed k the number of vertices of a k-coil may even be exponential with n. We introduce a dragon, which is an induced tree in a hypercube, and its generalization a k-dragon which preserves distances between its every two vertices at distance at most k−1 in hypercube. By proving a specific lemma from my Bachelor thesis that was previously verified by a computer, we finish the proof of the theorem regarding Hamiltonian laceability of hypercubes without n-dragons.
|
|
|
Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
Pěgřímek, David ; Gregor, Petr (advisor) ; Dvořák, Tomáš (referee)
In 2001 Stephen Locke conjectured that for every balanced set F of 2k faulty vertices in the n-di- mensional hypercube Qn where n ≥ k + 2 and k ≥ 1 the graph Qn − F is hamiltonian. So far the conjecture remains open although partial results are known; some of them with additional conditions on the set F. We explore hamiltonicity of Qn − F if the set of faulty vertices F forms certain isometric subgraph in Qn. For an odd (even) isometric path P in Qn the graph Qn − V (P) is Hamiltonian laceable for every n ≥ 4 (resp. n ≥ 5). Although a stronger result is known, the method we use in proving the theorem allows us to obtain following results. Let C be an isometric cycle in Qn of length divisible by four for n ≥ 6. Then the graph Qn −V (C) is Hamiltonian laceable. Let T be an isometric tree in Qn with odd number of edges and let S be an isometric tree in Qm with even number of edges. For every n ≥ 4, m ≥ 5 the graphs Qn −T and Qm −S are Hamiltonian laceable. A part of the proof is verified by a computer. 1
|
|
|
Rozklady propojovacích sítí na dlouhé cesty
Měkuta, Kryštof ; Gregor, Petr (advisor) ; Dvořák, Tomáš (referee)
❚✐t❧❡✿ P❛rt✐t✐♦♥s ♦❢ ✐♥t❡r❝♦♥♥❡❝t✐♦♥ ♥❡t✇♦r❦s ✐♥t♦ ❧♦♥❣ ♣❛t❤s ❆✉t❤♦r✿ ❑r②➨t♦❢ ▼➙❦✉t❛ ❉❡♣❛rt♠❡♥t✿ ❉❡♣❛rt♠❡♥t ♦❢ ❚❤❡♦r❡t✐❝❛❧ ❈♦♠♣✉t❡r ❙❝✐❡♥❝❡ ❛♥❞ ▼❛t❤❡♠❛t✐❝❛❧ ▲♦❣✐❝ ❙✉♣❡r✈✐s♦r✿ ▼❣r✳ P❡tr ●r❡❣♦r✱ P❤✳❉✳✱ ❑❚■▼▲ ❆❜str❛❝t✿ ❲❡ s✉r✈❡② s♦♠❡ ❜❛s✐❝ ♣r♦♣❡rt✐❡s ♦❢ s❡❧❡❝t❡❞ ✐♥t❡r❝♦♥♥❡❝t✐♦♥ ♥❡t✇♦r❦s✱ ♠♦r❡ ♣r❡❝✐s❡❧② ♠♦❞✐✜❝❛t✐♦♥s ♦❢ ❤②♣❡r❝✉❜❡s✳ ■♥ ♣❛rt✐❝✉❧❛r✱ ✇❡ st✉❞② ❢❛✉❧t✲t♦❧❡r❛♥❝❡ ♦❢ ❛✉❣♠❡♥t❡❞ ❝✉❜❡s ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ❡①✐st❡♥❝❡ ♦❢ ❍❛♠✐❧t♦♥✐❛♥ ❝②❝❧❡s✳ ❲❡ ❛❧✲ s♦ ♣r❡s❡♥t ❛ ♠❡t❤♦❞ t♦ ❝♦♥str✉❝t ♠❛♥② s♣❛♥♥✐♥❣ s✉❜❣r❛♣❤s ♦❢ AQn ✐s♦♠♦r♣❤✐❝ t♦ Qn ✉s✐♥❣ ❡❧❡♠❡♥t❛r② ❢❛❝ts ❢r♦♠ ❧✐♥❡❛r ❛❧❣❡❜r❛✳ ❲❡ ♣r♦✈❡ t❤❛t n✲❞✐♠❡♥s✐♦♥❛❧ ❛✉❣♠❡♥t❡❞ ❝✉❜❡ AQn ✇✐t❤ f ❢❛✉❧t② ❡❞❣❡s ❝♦♥t❛✐♥s ❛ ❝♦♣② ♦❢ n✲❞✐♠❡♥s✐♦♥❛❧ ❤②♣❡r✲ ❝✉❜❡ Qn ✇✐t❤ ❛t ♠♦st n 2n−1 f ❢❛✉❧t② ❡❞❣❡s✳ ❯s✐♥❣ t❤✐s r❡s✉❧t ✇❡ ❛r❡ ❛❜❧❡ t♦ ❡❛s✐❧② tr❛♥s❢❡r s❡✈❡r❛❧ ♣r♦♣❡rt✐❡s ♦❢ Qn ✇✐t❤ ❢❛✉❧t② ❡❞❣❡s t♦ AQn ✇✐t❤ ✭♠♦r❡✮ ❢❛✉❧t② ❡❞❣❡s✳ ❆♣♣❧②✐♥❣ s✐♠✐❧❛r ♠❡t❤♦❞✱ ✇❡ ❛❧s♦ s❤♦✇ t❤❛t ✐❢ f ≤ 3n−7 ❛♥❞ ❡✈❡r② ✈❡rt❡① ♦❢ AQn ✐s ✐♥❝✐❞❡♥t t♦ ❛t ❧❡❛st t✇♦ ♥♦♥✲❢❛✉❧t② ❡❞❣❡s✱ t❤❡♥ AQn ❤❛s ❛ ♥♦♥✲❢❛✉❧t② ❤❛♠✐❧t♦♥✐❛♥ ❝②❝❧❡✳ ▼♦r❡♦✈❡r✱ ✇❡ s❤♦✇ t❤❛t ❡✈❡r② t✇♦ ♠♦♥♦♠♦r♣❤✐s♠s ♦❢ G1 t♦ AQn ❛♥❞ G2 t♦ AQm ❝❛♥ ❜❡ ❝♦♠♣♦s❡❞ ✐♥t♦ ❛ ♠♦♥♦♠♦r♣❤✐s♠ ♦❢ t❤❡ ❈❛rt❡s✐❛♥ ♣r♦❞✉❝t G1 G2 t♦ AQn+m✳ ❑❡②✇♦r❞s✿ ❤②♣❡r❝✉❜❡✱ ❛✉❣♠❡♥t❡❞ ❝✉❜❡✱ ❤❛♠✐❧t♦♥✐❝✐t②✱ ❢❛✉❧t② ❡❞❣❡s
|
guest ::
